package com.yoshino.leetcode.improve40.twentyninth;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    List<String> res = new ArrayList<>();

    public List<String> generateParenthesis(int n) {
        // 回溯
        StringBuilder sb = new StringBuilder();
//        dfs(n, n, sb);
        dfs(n, 0, 0, sb);
        return res;
    }

    private void dfs(int left, int right, StringBuilder sb) {
        if (left == 0 && right == 0) {
            res.add(sb.toString());
            return;
        }
        // 保证括号合法性
        // 左右两边大于0，左括号剩余大于右括号
        if (left < 0 || right < 0 || left > right) {
            return;
        }
        dfs(left - 1, right, sb.append("("));
        sb.deleteCharAt(sb.length() - 1);
        dfs(left, right - 1, sb.append(")"));
        sb.deleteCharAt(sb.length() - 1);
    }

    private void dfs(int n, int left, int right, StringBuilder sb) {
        if (sb.length() == 2 * n) {
            res.add(sb.toString());
            return;
        }
        // 保证括号合法性
        // 左右两边大于0，
        if (left < n) {
            sb.append("(");
            dfs(n, left + 1, right, sb);
            sb.deleteCharAt(sb.length() - 1);
        }
        //左括号大于右括号
        if (right < left) {
            sb.append(")");
            dfs(n, left, right + 1, sb);
            sb.deleteCharAt(sb.length() - 1);
        }
    }

    List<List<String>> preRes = new ArrayList<>();
    List<String> tmp = new ArrayList<>();
    int n;
    // 动态规划
    boolean[][] dp;
    public String[][] partition(String s) {
        // 回溯 + 动态规划预处理：重复判断子回文串情况
        this.n = s.length();
        dp = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        // 对角线 往上依次判断
        for (int j = 0; j < n; j++) {
            for (int i = j; i >= 0; i--) {
                if (j - i < 3) {
                    // 1, 2, 1
                    dp[i][j] = s.charAt(i) == s.charAt(j);
                } else {
                    // 1, 2, 2, 1
                    dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1];
                }
            }
        }
        dfs(s, 0);
        int m = preRes.size();
        String[][] res = new String[m][];
        for (int i = 0; i < m; i++) {
            int n = preRes.get(i).size();
            res[i] = new String[n];
            for (int j = 0; j < n; j++) {
                res[i][j] = preRes.get(i).get(j);
            }
        }
        return res;
    }

    private void dfs(String s, int ind) {
        if (ind == n) {
            preRes.add(new ArrayList<>(tmp));
            return;
        }
        for (int i = ind; i < n; i++) {
            if (dp[ind][i]) {
                tmp.add(s.substring(ind, i + 1));
                dfs(s, i + 1);
                tmp.remove(tmp.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        String[][] googles = new Solution().partition("google");
        for (String[] google : googles) {
            System.out.println(Arrays.toString(google));
        }
    }

    public List<String> restoreIpAddresses(String s) {
        if (s.length() < 4 || s.length() > 12) {
            return res;
        }
        dfsSpilt(s, 0);
        return res;
    }

    private void dfsSpilt(String s, int ind) {
        if (tmp.size() == 4) {
            // 拆分完
            if (ind == s.length()) {
                res.add(turnIp(tmp));
                return;
            }
        }
        int max = Math.min(s.length(), ind + 3);
        for (int i = ind; i < max; i++) {
            String substring = s.substring(ind, i + 1);
            int num = Integer.parseInt(substring);
            // 前导不能为0
            if ((substring.length() > 1 && substring.startsWith("0")) || num > 255) {
                break;
            }
            tmp.add(substring);
            dfsSpilt(s, i + 1);
            tmp.remove(tmp.size() - 1);
        }
    }

    private String turnIp(List<String> tmp) {
        StringBuilder sb = new StringBuilder();
        for (String s : tmp) {
            sb.append(s);
            sb.append(".");
        }
        return sb.deleteCharAt(sb.length() - 1).toString();
    }
}